package com.data_structure_algorithm.data_structure.graph;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Authror PABLO
 * @Date 2022/4/4 14:04
 * @Desc 图的广度优先
 */
public class BFS {
    public static void main(String[] args) {
        BFS bfs = new BFS(5);
        String[] vertexVal = {"A", "B", "C", "D", "E"};

        //添加顶点
        for (int i = 0; i < vertexVal.length; i++) {
            bfs.addVertex(vertexVal[i]);
        }

        //建立顶点之间边的关系
        bfs.addEdge(0, 1, 1);
        bfs.addEdge(0, 2, 1);
        bfs.addEdge(1, 2, 1);
        bfs.addEdge(1, 3, 1);
        bfs.addEdge(1, 4, 1);


        //深度优先查找
        bfs.bfs();

        //显示矩阵
        bfs.showMatrix();


    }


    //存储顶点
    List<String> vertex;
    //矩阵,大小为顶点*顶点
    int[][] matrix;
    //边
    int edge;

    //记录是否被访问
    boolean[] isVis;


    //初始化矩阵和list
    public BFS(int n) {
        //初始化矩阵
        this.matrix = new int[n][n];
        //初始化访问标记数组
        this.isVis = new boolean[n];
        //通过顶点的个数创建顶点集合
        this.vertex = new ArrayList<>(n);
    }

    public void bfs() {
        for (int i = 0; i < getVerNum(); i++) {
            if (!isVis[i]) {
                bfs(i);
            }
        }
    }


    /**
     * @Description:广度遍历
     * @Author: PABLO
     * @Date: 2022/4/4 22:40
     * @Params: [index]
     * @Return: void
     **/
    private void bfs(int index) {
        //队列头结点下标
        int headIndex;

        //该头结点的邻接点下标
        int headNeighborIndex;

        //队列,记录节点访问顺序，即记录本行中有哪些节点  以行为单位，第一行先访问所有，而后在第二行
        Deque<Integer> deque = new LinkedList<>();


        //打印当前 初始节点
        System.out.println(vertex.get(index) + "->");
        //标记
        isVis[index] = true;
        //将此节点加入队列   队尾加入队头取出
        deque.addLast(index);
        //只要队列不为空 就处理，将本行中所有的节点依次取出，直至空，进入下一轮，即外围行的变化
        while (!deque.isEmpty()) {
            //取出队列头下标
            headIndex = deque.removeFirst();
            //得到头下标的邻接节点
            headNeighborIndex = this.getCurVisPostIndex(headIndex);
            while (headNeighborIndex != -1) {
                //判断该邻接点是否被访问过
                boolean isVi = isVis[headNeighborIndex];
                //未被访问过
                if (!isVi) {
                    //打印当前节点
                    System.out.println(getVerByIndex(headNeighborIndex) + "->");
                    //标记
                    isVis[headNeighborIndex] = true;

                    //入队列
                    deque.addLast(headNeighborIndex);
                }


                //在该行headNeighborIndex后继续往后找邻接点   这里是横向找
                headNeighborIndex = this.getPostByPreIndex(headIndex, headNeighborIndex);
            }

        }

    }

    /**
     * @Description:通过当前下标（邻接点）找到下一个邻接点 根据行  横着找列
     * 依次返回curIndex行所在的所有列
     * @Author: PABLO
     * @Date: 2022/4/4 16:24
     * @Params: [curIndex]
     * @Return: int 下标值
     **/
    private int getCurVisPostIndex(int curIndex) {
        for (int i = 0; i < vertex.size(); i++) {
            //>0是因为当前将1设置为有连接关系，0位没有连接
            //行代表当前index对应的当前顶点
            //列代表当前  index（顶点）行  和哪些顶点<列> 有链接关系
            if (this.matrix[curIndex][i] > 0) return i;//返回下一个和当前节点行有联系的节点列
        }
        return -1;
    }

    /**
     * @Description: 从v1所在行，v2列的位置，继续向后找可访问的列
     * @Author: PABLO
     * @Date: 2022/4/4 16:35
     * @Params: [v1 当前节点
     * v2 当前节点的下一个节点 ]
     * @Return: int
     **/
    private int getPostByPreIndex(int v1, int v2) {
        for (int i = v2 + 1; i < vertex.size(); i++) {
            //[v1][i]  v1行的v2列的后面找值>0的
            if (this.matrix[v1][i] > 0) return i;
        }
        return -1;
    }

    /**
     * @Description:添加顶点
     * @Author: PABLO
     * @Date: 2022/4/4 14:13
     * @Params: [verName]
     * @Return: void
     **/
    public void addVertex(String verName) {
        this.vertex.add(verName);
    }

    /**
     * @Description:
     * @Author: PABLO
     * @Date: 2022/4/4 14:15
     * @Params: [v1 顶点下标, v2 顶点下标, weight 表示关联关系，如1为关联 0为不关联]
     * @Return: void
     **/
    public void addEdge(int v1, int v2, int weight) {
        //无向图的双端关联
        this.matrix[v1][v2] = weight;
        this.matrix[v2][v1] = weight;
        edge++;
    }

    /**
     * @Description:根据两个顶点下标获取对应权值
     * @Author: PABLO
     * @Date: 2022/4/4 15:40
     * @Params: [v1, v2]
     * @Return: int
     **/
    public int getWeight(int v1, int v2) {
        return this.matrix[v1][v2];

    }

    /**
     * @Description:显示矩阵
     * @Author: PABLO
     * @Date: 2022/4/4 15:42
     * @Params: []
     * @Return: void
     **/
    public void showMatrix() {

        for (int[] item : this.matrix) {
            for (int element : item) {
                System.out.print(" " + element);
            }
            System.out.println();
        }
    }


    /**
     * @Description: 返回节点个数
     * @Author: PABLO
     * @Date: 2022/4/4 14:18
     * @Params: []
     * @Return: int
     **/
    public int getVerNum() {
        return this.vertex.size();
    }

    /**
     * @Description: 返回边个数
     * @Author: PABLO
     * @Date: 2022/4/4 14:18
     * @Params: []
     * @Return: int
     **/
    public int getMatNum() {
        return this.edge;
    }

    /**
     * @Description: 根据下标得到对应顶点值
     * @Author: PABLO
     * @Date: 2022/4/4 14:20
     * @Params: [index]
     * @Return: java.lang.String
     **/
    public String getVerByIndex(int index) {
        return this.vertex.get(index);
    }
}
